# -*- coding: utf-8 -*-

"""剑指 Offer II 118. 多余的边
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。
图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

示例 1：
输入: edges = [[1,2],[1,3],[2,3]]
输出: [2,3]

示例 2：
输入: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
输出: [1,4]

提示:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的 """

class Solution:
    """按常规操作，应该这样理解：
    树结构多了一条边，就形成了一个环结构。所以一般的处理步骤是找到环，然后遍历这些边，发现边的两个顶点都在环上便可以将这条边删去，需要遍历完，删掉最后一条组成环的边。
    这个解法，可以利用拓扑排序实现环检测，并定位到环结构。
    
    不过按题目要求，只需要给出最后一条组成环的边。这是解体的关键点。
    看题解，可以利用并查集来实现，我这时候对并查集的使用还不是很熟练，不一定灵活地转过弯。
    仔细研究这个题，n个顶点，(n-1)条边组成树，另外1条边成环，没有多一条浪费。
    在条件的约束下，单说（n-1）条边的树。每一条边的加入都是对树的扩容，这条边加入前，是两棵互相独立的树。
    而成环的边加入的时候，是在同一颗树下操作。所以就是因为这条边的加入，成环了。
    
    那么这条边是不是组成环的最后一条边呢？当然是，就因为这条边的加入才立马成环啊。"""
    def findRedundantConnection(self, edges: list) -> list:
        size = len(edges)+1
        node_group = list(range(size))    # 为了方便计算，1-n号顶点，对应1-n号偏移量，0偏移量不做使用

        def find(i):
            if node_group[i] != i:
                node_group[i] = find(node_group[i])
            return node_group[i]

        for nx, ny in edges:
            gx, gy = find(nx), find(ny)
            if gx == gy:
                return [nx, ny]
            else:
                node_group[gx] = gy


if __name__ == '__main__':
    print(Solution().findRedundantConnection([[1,2],[1,3],[2,3]]))
    print(Solution().findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]]))
